{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Mutated Array Closest to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findBestValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #转变数组后最接近目标值的数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code> 和一个目标值&nbsp;<code>target</code> ，请你返回一个整数&nbsp;<code>value</code>&nbsp;，使得将数组中所有大于&nbsp;<code>value</code> 的值变成&nbsp;<code>value</code> 后，数组的和最接近&nbsp; <code>target</code>&nbsp;（最接近表示两者之差的绝对值最小）。</p>\n",
    "\n",
    "<p>如果有多种使得和最接近&nbsp;<code>target</code>&nbsp;的方案，请你返回这些整数中的最小值。</p>\n",
    "\n",
    "<p>请注意，答案不一定是&nbsp;<code>arr</code> 中的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,9,3], target = 10\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,3,5], target = 10\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [60864,25176,27249,21296,20204], target = 56803\n",
    "<strong>输出：</strong>11361\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^4</code></li>\n",
    "\t<li><code>1 &lt;= arr[i], target &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-mutated-array-closest-to-target](https://leetcode.cn/problems/sum-of-mutated-array-closest-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-mutated-array-closest-to-target](https://leetcode.cn/problems/sum-of-mutated-array-closest-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,9,3]\\n10', '[2,3,5]\\n10', '[60864,25176,27249,21296,20204]\\n56803']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = [0]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1] + num)\n",
    "        \n",
    "        l, r, ans = 0, max(arr), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            it = bisect.bisect_left(arr, mid)\n",
    "            cur = prefix[it] + (n - it) * mid\n",
    "            if cur <= target:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        def check(x):\n",
    "            return sum(x if num >= x else num for num in arr)\n",
    "        \n",
    "        choose_small = check(ans)\n",
    "        choose_big = check(ans + 1)\n",
    "        return ans if abs(choose_small - target) <= abs(choose_big - target) else ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s<=target:\n",
    "            return max(arr)\n",
    "        avg = target//n\n",
    "        less = 0\n",
    "        new = arr\n",
    "        while avg>min(new) and avg<max(new):\n",
    "            new = []\n",
    "            for num in arr:\n",
    "                if num <=avg:\n",
    "                    target-=num\n",
    "                else:\n",
    "                    new.append(num)\n",
    "            arr = new\n",
    "            n = len(arr)\n",
    "            avg = target//n\n",
    "\n",
    "        \n",
    "        \n",
    "        if target-avg*n>(avg+1)*n-target:\n",
    "            return avg+1\n",
    "        else:\n",
    "            return avg\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        pre = list(accumulate(arr, initial=0))\n",
    "        aver = target // len(arr)\n",
    "        delta, ret = inf, 0\n",
    "        while aver:\n",
    "            idx = bisect_left(arr, aver)\n",
    "            tmp = abs(pre[idx] + (len(arr) - idx) * aver - target)\n",
    "            if tmp < delta:\n",
    "                delta, ret = tmp, aver\n",
    "            else:\n",
    "                break\n",
    "            aver += 1\n",
    "        return min(ret, arr[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        def cal(arr, value, pre_sum):\n",
    "            left, right = 0, len(arr) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr[mid] < value:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return pre_sum[left] + (len(arr) - left) * value\n",
    "\n",
    "        def binary_search(arr, target, pre_sum):\n",
    "            left, right = 0, arr[-1]\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if cal(arr, mid, pre_sum) < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        pre_sum = [0 for _ in range(len(arr))]\n",
    "        arr.sort()\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            pre_sum[i] = pre_sum[i - 1] + arr[i - 1]\n",
    "\n",
    "        value = binary_search(arr, target, pre_sum)\n",
    "        sum_1 = cal(arr, value, pre_sum)\n",
    "        sum_2 = cal(arr, value - 1, pre_sum)\n",
    "        diff_1 = abs(sum_1 - target)\n",
    "        diff_2 = abs(sum_2 - target)\n",
    "        return value if diff_1 < diff_2 else value - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        l,r = 0, max(arr)\n",
    "        ans = inf\n",
    "        while l<=r:\n",
    "            m = (l+r) >> 1\n",
    "            s = sum(min(x, m) for x in arr) \n",
    "            if s > target:\n",
    "                r = m-1\n",
    "            else: # s <= target\n",
    "                ans = m\n",
    "                l = m+1\n",
    "        choose_small = sum(min(x, ans) for x in arr) \n",
    "        choose_big = sum(min(x, ans+1) for x in arr) \n",
    "        return ans if abs(choose_small-target) <= abs(choose_big-target) else ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s<=target:\n",
    "            return max(arr)\n",
    "        avg = target//n\n",
    "        less = 0\n",
    "        new = arr\n",
    "        while avg>min(new) and avg<max(new):\n",
    "            new = []\n",
    "            for num in arr:\n",
    "                if num <=avg:\n",
    "                    target-=num\n",
    "                else:\n",
    "                    new.append(num)\n",
    "            arr = new\n",
    "            n = len(arr)\n",
    "            avg = target//n\n",
    "\n",
    "        \n",
    "        \n",
    "        if target-avg*n>(avg+1)*n-target:\n",
    "            return avg+1\n",
    "        else:\n",
    "            return avg\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "\n",
    "        pre =[0]+ list(accumulate(arr))\n",
    "\n",
    "        l,r =0,arr[-1]\n",
    "        ans = 0 \n",
    "        diff = target \n",
    "        for i in range(r+1): \n",
    "           j = bisect_right(arr,i)\n",
    "           s = pre[j]+(n-j)*i\n",
    "           if abs(s-target)<diff:\n",
    "               ans =i\n",
    "               diff = abs(s-target)\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "\n",
    "        pre =[0]+ list(accumulate(arr))\n",
    "\n",
    "        l,r =0,arr[-1]\n",
    "        # 双重二分\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            j = bisect_right(arr,mid)\n",
    "            s = pre[j]+(n-j)*mid\n",
    "            if s<target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        j0,j1 =bisect_right(arr,r-1),bisect_right(arr,r)\n",
    "        sum1 =pre[j0]+(n-j0)*(r-1)\n",
    "        sum2 = pre[j1]+(n-j1)*r\n",
    "        print(sum1,sum2)\n",
    "\n",
    "        return r-1 if abs(sum1-target) <=abs(sum2-target) else r\n",
    "\n",
    "\n",
    "        # for i in range(r+1): \n",
    "        #    j = bisect_right(arr,i)\n",
    "        #    s = pre[j]+(n-j)*i\n",
    "        #    if abs(s-target)<diff:\n",
    "        #        ans =i\n",
    "        #        diff = abs(s-target)\n",
    "        # return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算 value 对应的转变后的数组\n",
    "    def calc_sum(self, arr, value, pre_sum):\n",
    "        size = len(arr)\n",
    "        left, right = 0, size - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] < value:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return pre_sum[left] + (size - left) * value\n",
    "\n",
    "    # 查找使得转变后的数组和刚好大于等于 target 的 value\n",
    "    def binarySearchValue(self, arr, target, pre_sum):\n",
    "        left, right = 0, arr[-1]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calc_sum(arr, mid, pre_sum) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        size = len(arr)\n",
    "        arr.sort()\n",
    "        pre_sum = [0 for _ in range(size + 1)]\n",
    "\n",
    "        for i in range(size):\n",
    "            pre_sum[i + 1] = pre_sum[i] + arr[i]\n",
    "\n",
    "        value = self.binarySearchValue(arr, target, pre_sum)\n",
    "\n",
    "        sum_1 = self.calc_sum(arr, value, pre_sum)\n",
    "        sum_2 = self.calc_sum(arr, value - 1, pre_sum)\n",
    "        diff_1 = abs(sum_1 - target)\n",
    "        diff_2 = abs(sum_2 - target)\n",
    "\n",
    "        return value if diff_1 < diff_2 else value - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()  #arr升序排序处理\n",
    "        pre=0       #arr[](升序后)的前缀合（含首0）\n",
    "        for i, a in enumerate(arr):\n",
    "            k=len(arr)-i        # 后面还有k项，同时k也是S(a)在a=arr[i]处的斜率！\n",
    "            d=pre+a*k-target    #前i项和pre + 后k项全置为arr[i] 与 target差值\n",
    "            if d>=0: return a-(d+k//2)//k   #等价于 arr[i] - 四舍五入(d÷k) 。\n",
    "            pre+=a  #↑当d÷k的小数部分为0.5，则取1（注意整体是减去1）符合同近取小原则。\n",
    "        return arr[-1]  #for循环内无解，取arr[]最大值作为结果。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        l, r = 0, max(arr)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if sum(min(mid, v) for v in arr) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "\n",
    "        lsum, rsum = sum(min(l, v) for v in arr), sum(min(r, v) for v in arr)\n",
    "        return l if abs(lsum - target) <= abs(rsum - target) else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    # 方法一\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp1 = 0\n",
    "            for num in arr:\n",
    "                if num > mid:\n",
    "                    tmp1 += mid\n",
    "                else:\n",
    "                    tmp1 += num\n",
    "            if tmp1 >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        tmp1 = 0\n",
    "        for num in arr:\n",
    "            if num > left:\n",
    "                tmp1 += left\n",
    "            else:\n",
    "                tmp1 += num\n",
    "        \n",
    "        tmp2 = 0\n",
    "        for num in arr:\n",
    "            if num > left-1:\n",
    "                tmp2 += (left-1)\n",
    "            else:\n",
    "                tmp2 += num\n",
    "\n",
    "        if tmp1 - target < target - tmp2:\n",
    "            return left\n",
    "        else:\n",
    "            return left - 1\n",
    "    '''\n",
    "\n",
    "    # 方法二：定义函数\n",
    "    # 计算value对应的转变后的数组\n",
    "    def calc_sum(self, arr, value, pre_sum):\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] < value:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        # 这里left的含义是保留了原始的几个数\n",
    "        return pre_sum[left] + (n - left) * value\n",
    "    \n",
    "    # 查找使得转变后的数组和刚好大于等于target的value\n",
    "    def binarySearchValue(self, arr, pre_sum, target):\n",
    "        left = 0\n",
    "        right = arr[-1]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp = self.calc_sum(arr, mid, pre_sum)\n",
    "            if tmp < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        pre_sum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1] = pre_sum[i] + arr[i]\n",
    "\n",
    "        value = self.binarySearchValue(arr, pre_sum, target)\n",
    "        print(value)\n",
    "\n",
    "        sum1 = self.calc_sum(arr, value, pre_sum)\n",
    "        sum2 = self.calc_sum(arr, value-1, pre_sum)\n",
    "        print(sum1)\n",
    "        print(sum2)\n",
    "\n",
    "        return value if sum1 - target < target - sum2 else value - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        arr.append(10 ** 5)\n",
    "        if arr[0] * n >= target:\n",
    "            temp = target // n\n",
    "            if target - temp * n <= (temp + 1) * n - target:\n",
    "                return temp\n",
    "            else:\n",
    "                return temp + 1\n",
    "        prefix = 0\n",
    "        for i in range(n):\n",
    "            prefix += arr[i]\n",
    "            if prefix + (n - i - 1) * arr[i] <= target <= prefix + (n - i - 1) * arr[i+1]:\n",
    "                temp = (target - prefix) // (n - i - 1)\n",
    "                if target - prefix - (n - i - 1) * temp <= (n - i - 1) * (temp + 1) + prefix - target:\n",
    "                    return temp\n",
    "                else:\n",
    "                    return temp + 1\n",
    "        return arr[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 二分法 寻找小于等于某个数的最大值-左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <=target:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        sum1 = self.calculate(arr, right)\n",
    "        sum2 = self.calculate(arr, right - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right\n",
    "        return right-1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        s = [0] + list(accumulate(arr))\n",
    "        mi = inf\n",
    "        mx = max(arr)\n",
    "        n = len(arr)\n",
    "        for i in range(mx + 1):\n",
    "            r = bisect_right(arr, i)\n",
    "            d = abs(s[r] + i * (n - r) - target)\n",
    "            if d < mi:\n",
    "                mi = d\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        pre = [*accumulate(arr, initial=0)]\n",
    "\n",
    "        def get_total(v):\n",
    "            i = bisect_left(arr, v)\n",
    "            return (n - i) * v + pre[i]\n",
    "    \n",
    "        l = target // n\n",
    "        r = arr[-1]\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = get_total(mid)\n",
    "            if total > target:\n",
    "                r = mid - 1\n",
    "            elif total < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        return min((l-1, l, l+1), key=lambda i:abs(get_total(i) - target))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        sum1 = self.calculate(arr, right)\n",
    "        sum2 = self.calculate(arr, right - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right\n",
    "        return right - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        if sum(arr)<=target:\n",
    "            return max(arr)\n",
    "        l = len(arr)\n",
    "        left,right = target//l,min(max(arr),target)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            summ = 0\n",
    "            for v in arr:\n",
    "                summ +=min(v,mid)\n",
    "            if target<summ:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        summ,sumright,sumleft= 0,0,0 #二分法停止时有可能在target的左边，也有可能在右边，因此，比较相邻的三个和\n",
    "        for v in arr:\n",
    "            summ +=min(v,left)\n",
    "            sumright +=min(v,left+1)\n",
    "            sumleft +=min(v,left-1)\n",
    "        if abs(target-sumright)>=abs(target-summ):\n",
    "            return left if abs(target-summ)<abs(target-sumleft) else left-1\n",
    "        else:\n",
    "            return left+1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法一: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值 右边界搜索\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) > target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        sum1 = self.calculate(arr, right)\n",
    "        sum2 = self.calculate(arr, right - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right\n",
    "        return right - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        s = sum(arr)\n",
    "        n = len(arr)\n",
    "        pre = list(accumulate(arr, initial=0))\n",
    "        aver = target // n\n",
    "        if target == s:\n",
    "            return arr[-1]\n",
    "        else:\n",
    "            delta = inf\n",
    "            ret = 0\n",
    "            while aver:\n",
    "                idx = bisect_left(arr, aver)\n",
    "                tmp = abs(pre[idx] + (n - idx) * aver - target)\n",
    "                if tmp < delta:\n",
    "                   delta = tmp\n",
    "                   ret = aver\n",
    "                else:\n",
    "                    break\n",
    "                aver += 1\n",
    "        return ret if ret <= arr[-1] else arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        base = sum(arr)\n",
    "        acc = list(accumulate(arr, initial=0))\n",
    "        if base <= target:\n",
    "            return arr[-1]\n",
    "        low, high = 0, arr[-1]\n",
    "\n",
    "        def f(val):\n",
    "            idx = bisect_left(arr, val)\n",
    "            res = acc[idx] + (n - idx) * val\n",
    "            return res\n",
    "\n",
    "        l, r = low, high\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            a = f(mid)\n",
    "            if a < target:\n",
    "                l = mid\n",
    "                low = mid + 1\n",
    "            elif a == target:\n",
    "                return mid\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        low, high = 0, arr[-1]\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            a = f(mid)\n",
    "            if a > target:\n",
    "                r = mid\n",
    "                high = mid - 1\n",
    "            elif a == target:\n",
    "                return mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        if target - f(l) <= f(r) - target:\n",
    "            return l\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 二分法 寻找大于等于某个数的最小值-左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找大于等于target的最小值,左边界搜索\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "        return right-1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        arr.sort()\n",
    "        sum = 0\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(1, n + 1, 1):\n",
    "            pre[i] = sum + (n - i + 1) * arr[i - 1]\n",
    "            sum += arr[i - 1]\n",
    "        \n",
    "        ip = bisect_left(pre, target)\n",
    "        if ip == n + 1:\n",
    "            return arr[-1]\n",
    "        else:\n",
    "            unit = n - ip + 1\n",
    "            a = pre[ip] - target\n",
    "            b = target - pre[ip - 1]\n",
    "\n",
    "            if unit == 1:\n",
    "                return arr[ip - 1] - a\n",
    "            elif a % unit == 0 or a % unit < b % unit:\n",
    "                return arr[ip - 1] - a // unit\n",
    "            else:\n",
    "                return arr[ip - 1] - a // unit - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "       def g(k):\n",
    "          tt=0\n",
    "          for x in arr:\n",
    "             tt+=min(x,k)\n",
    "          return tt\n",
    "       l=0\n",
    "       r=max(arr)\n",
    "       while l<r:\n",
    "         m=(l+r)//2\n",
    "         if g(m)<target:\n",
    "           l=m+1\n",
    "         else:\n",
    "           r=m\n",
    "       if g(l)-target>=target-g(l-1):\n",
    "          return l-1\n",
    "       else:\n",
    "          return l                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()  #arr升序排序处理\n",
    "        pre=0       #arr[](升序后)的前缀合（含首0）\n",
    "        for i, a in enumerate(arr):\n",
    "            k=len(arr)-i        # 后面还有k项，同时k也是S(a)在a=arr[i]处的斜率！\n",
    "            d=pre+a*k-target    #前i项和pre + 后k项全置为arr[i] 与 target差值\n",
    "            if d>=0: return a-(d+k//2)//k   #等价于 arr[i] - 四舍五入(d÷k) 。\n",
    "            pre+=a  #↑当d÷k的小数部分为0.5，则取1（注意整体是减去1）符合同近取小原则。\n",
    "        return arr[-1]  #for循环内无解，取arr[]最大值作为结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 二分法 寻找大于等于某个数的最小值-左闭右闭区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找大于等于target的最小值\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) >= target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left,right=0,max(arr)\n",
    "        def check(val):\n",
    "            total=0\n",
    "            for i in arr:\n",
    "                total+=min(i,val)\n",
    "            return total\n",
    "        while left<right:\n",
    "            mid=(left+right)>>1\n",
    "            if check(mid)<target:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        x,y=check(left),check(left-1)\n",
    "        if x-target>=target-y: return left -1\n",
    "        else: return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        minn = arr[0]\n",
    "        maxn = arr[-1]\n",
    "        \n",
    "        if sum(arr)<=target:\n",
    "            return maxn\n",
    "        left = int(target/len(arr)) \n",
    "        right = maxn\n",
    "        res = maxn\n",
    "        dif = float('inf')\n",
    "        while left <=right:\n",
    "            mid = (left+right)//2\n",
    "            count = sum(i<mid for i in arr)\n",
    "            if sum(arr[:count])+mid*(len(arr)-count)==target:\n",
    "                return mid\n",
    "            if sum(arr[:count])+mid*(len(arr)-count)<target:\n",
    "                left = mid+1 \n",
    "                temp = abs(sum(arr[:count])+mid*(len(arr)-count)-target)\n",
    "                if dif>=temp:\n",
    "                    dif = temp \n",
    "                    res = mid\n",
    "            if sum(arr[:count])+mid*(len(arr)-count)>target:\n",
    "                right = mid -1\n",
    "                temp = abs(sum(arr[:count])+mid*(len(arr)-count)-target)\n",
    "                if dif>=temp:\n",
    "                    dif = temp \n",
    "                    res = mid\n",
    "        count1 = sum(i<(mid-1) for i in arr)\n",
    "        temp1 = abs(sum(arr[:count])+(mid-1)*(len(arr)-count)-target)\n",
    "        # if dif>temp\n",
    "        #     mid-1\n",
    "        count2 = sum(i<(mid+1) for i in arr)\n",
    "        temp2 = abs(sum(arr[:count])+(mid+1)*(len(arr)-count)-target)\n",
    "        if temp1<temp2:\n",
    "            midt = mid-1\n",
    "            temp = temp1\n",
    "        else:\n",
    "            midt = mid+1\n",
    "            temp = temp2\n",
    "        \n",
    "        \n",
    "        return mid if dif<temp else midt # 返回所有候选中的最小值\n",
    "\n",
    "        # left = 0 \n",
    "        # right = len(arr)-1\n",
    "        # if sum(arr)<=target:\n",
    "        #     return maxn\n",
    "        # res = maxn\n",
    "        # dif = float('inf')\n",
    "        # while left <=right:\n",
    "        #     mid = (left+right)//2\n",
    "        #     if arr[mid]*(right-mid+1)+sum(arr[:mid])==target:\n",
    "        #         return arr[mid]\n",
    "        #     if arr[mid]*(right-mid+1)+sum(arr[:mid])<target:\n",
    "        #         left = mid+1 \n",
    "        #         temp = abs(arr[mid]*(right-mid+1)+sum(arr[:mid])-target)\n",
    "        #         if dif>=temp:\n",
    "        #             dif = temp \n",
    "        #             res = arr[mid]\n",
    "        #     if arr[mid]*(right-mid+1)+sum(arr[:mid])>target:\n",
    "        #         right = mid - 1\n",
    "        #         temp = abs(arr[mid]*(right-mid+1)+sum(arr[:mid])-target)\n",
    "        #         if dif>=temp:\n",
    "        #             dif = temp \n",
    "        #             res = arr[mid]\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        arr.sort()\n",
    "        sum = 0\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(1, n + 1, 1):\n",
    "            pre[i] = sum + (n - i + 1) * arr[i - 1]\n",
    "            sum += arr[i - 1]\n",
    "        \n",
    "        ip = bisect_left(pre, target)\n",
    "        if ip == n + 1:\n",
    "            return arr[-1]\n",
    "        else:\n",
    "            unit = n - ip + 1\n",
    "            a = pre[ip] - target\n",
    "            b = target - pre[ip - 1]\n",
    "            if a % unit < b % unit:\n",
    "                return arr[ip - 1] - a // unit\n",
    "            else:\n",
    "                return (arr[ip - 2] if ip > 1 else 0) + b // unit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法一: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) > target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        sum1 = self.calculate(arr, right)\n",
    "        sum2 = self.calculate(arr, right - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right\n",
    "        return right - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右闭区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        size = len(arr)\n",
    "        arr.sort()\n",
    "        if sum(arr) <= target:\n",
    "            return arr[-1]\n",
    "        remain = size\n",
    "        for i in range(size):\n",
    "            average = round( target / remain)\n",
    "            if arr[i] <= average :\n",
    "                remain -=1\n",
    "                target = target - arr[i]\n",
    "            else:\n",
    "                return average"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = list(accumulate(arr))\n",
    "        min_ = floor(target / n)\n",
    "        if arr[0] >= min_:\n",
    "            return min_ if abs(min_ * n - target) <= abs((min_ + 1) * n - target) else min_ + 1\n",
    "        if prefix[n-1] <= target:\n",
    "            return arr[-1]\n",
    "        \n",
    "        ans, diff = 0, target\n",
    "        for num in sorted(list(set(arr)), key = arr.index)[:-1]:\n",
    "            it = bisect.bisect_right(arr, num)\n",
    "            min_ = round((target - prefix[it-1]) / (n - it))\n",
    "            cur = prefix[it-1] + (n - it) * min_\n",
    "            if abs(cur - target) < diff and num <= min_ <= arr[it]:\n",
    "                ans, diff = min(min_, arr[it]), abs(cur - target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    # 方法一\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp1 = 0\n",
    "            for num in arr:\n",
    "                if num > mid:\n",
    "                    tmp1 += mid\n",
    "                else:\n",
    "                    tmp1 += num\n",
    "            if tmp1 >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        tmp1 = 0\n",
    "        for num in arr:\n",
    "            if num > left:\n",
    "                tmp1 += left\n",
    "            else:\n",
    "                tmp1 += num\n",
    "        \n",
    "        tmp2 = 0\n",
    "        for num in arr:\n",
    "            if num > left-1:\n",
    "                tmp2 += (left-1)\n",
    "            else:\n",
    "                tmp2 += num\n",
    "\n",
    "        if tmp1 - target < target - tmp2:\n",
    "            return left\n",
    "        else:\n",
    "            return left - 1\n",
    "    '''\n",
    "\n",
    "    # 方法二：定义函数\n",
    "    # 计算value对应的转变后的数组\n",
    "    def calc_sum(self, arr, value, pre_sum):\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] < value:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        # 这里left的含义是保留了原始的几个数\n",
    "        return pre_sum[left] + (n - left) * value\n",
    "    \n",
    "    # 查找使得转变后的数组和刚好大于等于target的value\n",
    "    def binarySearchValue(self, arr, pre_sum, target):\n",
    "        left = 0\n",
    "        right = arr[-1]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp = self.calc_sum(arr, mid, pre_sum)\n",
    "            if tmp < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        pre_sum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1] = pre_sum[i] + arr[i]\n",
    "\n",
    "        value = self.binarySearchValue(arr, pre_sum, target)\n",
    "\n",
    "        sum1 = self.calc_sum(arr, value, pre_sum)\n",
    "        sum2 = self.calc_sum(arr, value-1, pre_sum)\n",
    "\n",
    "        return value if sum1 - target < target - sum2 else value - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        def calc(arr, value, pre_sum):\n",
    "            left, right = 0, len(arr) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr[mid] < value:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return pre_sum[left] + (len(arr) - left) * value\n",
    "\n",
    "        def binary_search(arr, target, pre_sum):\n",
    "            left, right = 0, arr[-1]\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if calc(arr, mid, pre_sum) < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        arr.sort()\n",
    "        pre_sum = [0 for _ in range(len(arr))]\n",
    "        for i in range(1, len(arr)):\n",
    "            pre_sum[i] = pre_sum[i - 1] + arr[i - 1]\n",
    "        value = binary_search(arr, target, pre_sum)\n",
    "        sum_1 = calc(arr, value, pre_sum)\n",
    "        sum_2 = calc(arr, value - 1, pre_sum)\n",
    "        diff_1 = abs(sum_1 - target)\n",
    "        diff_2 = abs(sum_2 - target)\n",
    "\n",
    "        return value if diff_1 < diff_2 else value - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        l=len(arr)\n",
    "        for i in range(l):\n",
    "            avg=target/(l-i)\n",
    "            if arr[i]>avg: return round(avg-0.1+0.01)\n",
    "            target-=arr[i]\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = [0] + list(accumulate(arr))\n",
    "        \n",
    "        r, ans, diff = max(arr), 0, target\n",
    "        for i in range(1, r + 1):\n",
    "            it = bisect.bisect_left(arr, i)\n",
    "            cur = prefix[it] + (n - it) * i\n",
    "            if abs(cur - target) < diff:\n",
    "                ans, diff = i, abs(cur - target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右闭区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        sum1 = self.calculate(arr, right + 1)\n",
    "        sum2 = self.calculate(arr, right)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right + 1\n",
    "        return right\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右开区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        sum1 = self.calculate(arr, right)\n",
    "        sum2 = self.calculate(arr, right - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return right\n",
    "        return right - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        pre = [*accumulate(arr, initial=0)]\n",
    "        n = len(arr)\n",
    "        l = target // n\n",
    "        r = arr[-1]\n",
    "\n",
    "        def get_total(v):\n",
    "            i = bisect_left(arr, v)\n",
    "            return (n - i) * v + pre[i]\n",
    "\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = get_total(mid)\n",
    "\n",
    "            if total > target:\n",
    "                r = mid - 1\n",
    "            elif total < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        return min(range(l-1, l+2), key=lambda i:abs(get_total(i) - target))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        presum = [0]\n",
    "        for a in arr:\n",
    "            presum.append(presum[-1]+a)\n",
    "        if(presum[-1] <= target):\n",
    "            return arr[-1]\n",
    "        def getSum(x):\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(arr[mid] <= x):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return presum[left] + x*(n-left)\n",
    "        left, right = 0, 10**5\n",
    "        while(left <= right):\n",
    "            mid = (left+right)>>1\n",
    "            if(getSum(mid) >= target):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        mindiff = float('inf')\n",
    "        result = None\n",
    "        for num in range(right, left+1):\n",
    "            if(abs(getSum(num)-target) < mindiff):\n",
    "                result = num \n",
    "                mindiff = abs(getSum(num)-target)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        summ = sum(arr)\n",
    "        if summ<=target:\n",
    "            return max(arr)\n",
    "        l = len(arr)\n",
    "        val = target//l\n",
    "        summ,last = 0,0\n",
    "        while summ<target:\n",
    "            last = summ\n",
    "            summ = 0\n",
    "            for i in range(l):\n",
    "                summ +=arr[i] if val>arr[i] else val\n",
    "            val +=1\n",
    "        return val-2 if abs(target-summ)>=abs(target-last) else val-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        l, r = 0, max(arr)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if sum(min(mid, v) for v in arr) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "\n",
    "        lsum, rsum = sum(min(l, v) for v in arr), sum(min(r, v) for v in arr)\n",
    "        return l if abs(lsum - target) <= abs(rsum - target) else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        # 给出此数组中的最小值以及最大值\n",
    "        left, right = 0, max(arr)\n",
    "        # 求和，如果target大于等于数组sum的和，直接返回数组中的最大值\n",
    "        # 因为取最大值以上也只能是原本的和，如果target比原本的和还大，那么最接近也就是取到最大值了\n",
    "        sum_1 = sum(arr)\n",
    "        if sum_1 <= target:\n",
    "            print('A')\n",
    "            return right\n",
    "        else:\n",
    "            while left < right:\n",
    "                mid = int(left + (right - left)/2)\n",
    "                sum_left = 0\n",
    "                cnt = 0\n",
    "                print(left, mid, right)\n",
    "                # 计算value = mid下得到的求和值sum_2\n",
    "                for i in range(0, n): # range的最后一个数不计入\n",
    "                    if arr[i] >= mid:\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        sum_left += arr[i]\n",
    "                sum_2 = cnt*mid + sum_left\n",
    "                print('sum_2 =',sum_2)\n",
    "                # 相差为0时，可以直接获得最优方案\n",
    "                if sum_2 == target:\n",
    "                    print('B')\n",
    "                    print('\\n')\n",
    "                    return mid\n",
    "                # 若有偏差时，\n",
    "                elif (abs(sum_2 -target)) > (abs(sum_2 + cnt - target)):\n",
    "                    print('C1')\n",
    "                    print('\\n')\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    print('C2')\n",
    "                    print('\\n')\n",
    "                    right = mid\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        l, r = 0, max(arr)\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if sum(min(mid, v) for v in arr) >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "\n",
    "        lsum, rsum = sum(min(l, v) for v in arr), sum(min(r, v) for v in arr)\n",
    "        return l if abs(lsum - target) <= abs(rsum - target) else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        size = len(arr)\n",
    "        arr.sort()\n",
    "        if sum(arr) <= target:\n",
    "            return arr[-1]\n",
    "        remain = size\n",
    "        for i in range(size):\n",
    "            average = round( target / remain)\n",
    "            if arr[i] <= average :\n",
    "                remain -=1\n",
    "                target = target - arr[i]\n",
    "            else:\n",
    "                return average\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "#         arr.sort()\n",
    "#         n = len(arr)\n",
    "#         prefix = [0]\n",
    "#         for num in arr:\n",
    "#             prefix.append(prefix[-1] + num)\n",
    "        \n",
    "#         r, ans, diff = max(arr), 0, target\n",
    "#         for i in range(1, r + 1):\n",
    "#             it = bisect.bisect_left(arr, i)\n",
    "#             cur = prefix[it] + (n - it) * i\n",
    "#             if abs(cur - target) < diff:\n",
    "#                 ans, diff = i, abs(cur - target)\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = [0]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1] + num)\n",
    "        \n",
    "        l, r, ans = 0, max(arr), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            it = bisect.bisect_left(arr, mid)\n",
    "            cur = prefix[it] + (n - it) * mid\n",
    "            if cur <= target:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        def check(x):\n",
    "            return sum(x if num >= x else num for num in arr)\n",
    "        \n",
    "        choose_small = check(ans)\n",
    "        choose_big = check(ans + 1)\n",
    "        return ans if abs(choose_small - target) <= abs(choose_big - target) else ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        presum = [0]\n",
    "        for a in arr:\n",
    "            presum.append(presum[-1]+a)\n",
    "        if(presum[-1] <= target):\n",
    "            return arr[-1]\n",
    "        def getSum(x):\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(arr[mid] <= x):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return presum[left] + x*(n-left)\n",
    "        left, right = 0, 10**5\n",
    "        while(left <= right):\n",
    "            mid = (left+right)>>1\n",
    "            print(mid , getSum(mid))\n",
    "            if(getSum(mid) >= target):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        mindiff = float('inf')\n",
    "        result = None\n",
    "        for num in range(right, left+1):\n",
    "            if(abs(getSum(num)-target) < mindiff):\n",
    "                result = num \n",
    "                mindiff = abs(getSum(num)-target)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 二分法\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找大于等于target的最小值\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        prex_sum=[0]\n",
    "        for num in arr:\n",
    "            prex_sum.append(prex_sum[-1]+num)\n",
    "        \n",
    "        r=arr[-1]\n",
    "        res=0\n",
    "        diff=target\n",
    "        for i in range(1,r+1):\n",
    "            index=self.binarySearch(arr,i)\n",
    "            total=prex_sum[index]+ i*(n-index)\n",
    "            if abs(total-target)<diff:\n",
    "                res,diff=i,abs(total-target)\n",
    "        return res\n",
    "    def binarySearch(self,arr,i):\n",
    "        l,r=0,len(arr)-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if arr[mid]<i:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        def check(m):\n",
    "            return sum(min(n,m) for n in arr)\n",
    "\n",
    "        l,r=1,max(arr)\n",
    "        while l<r:\n",
    "            m=(l+r)>>1\n",
    "            if check(m)<target: l=m+1\n",
    "            else: r=m\n",
    "        return min(l-1,l, key=lambda x: abs(check(x)-target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "    #     arr.sort()\n",
    "    #     n=len(arr)\n",
    "    #     prex_sum=[0]\n",
    "    #     for num in arr:\n",
    "    #         prex_sum.append(prex_sum[-1]+num)\n",
    "        \n",
    "    #     r=arr[-1]\n",
    "    #     res=0\n",
    "    #     diff=target\n",
    "    #     for i in range(1,r+1):\n",
    "    #         index=self.binarySearch(arr,i)\n",
    "    #         total=prex_sum[index]+ i*(n-index)\n",
    "    #         if abs(total-target)<diff:\n",
    "    #             res,diff=i,abs(total-target)\n",
    "    #     return res\n",
    "    # def binarySearch(self,arr,i):\n",
    "    #     l,r=0,len(arr)-1\n",
    "    #     while l<r:\n",
    "    #         mid=(l+r)//2\n",
    "    #         if arr[mid]<i:\n",
    "    #             l=mid+1\n",
    "    #         else:\n",
    "    #             r=mid\n",
    "    #     return l\n",
    "\n",
    "\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        prex_sum=[0]\n",
    "        for num in arr:\n",
    "            prex_sum.append(prex_sum[-1]+num)\n",
    "        \n",
    "        ans=-1\n",
    "        l,r=0,arr[-1]\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            index=self.binarySearch(arr,mid)\n",
    "            curr=prex_sum[index]+mid*(n-index)\n",
    "            if curr<=target:\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        def check(x):\n",
    "            return sum(x if num>=x else num for num in arr)\n",
    "        choose_large=check(r)\n",
    "        choose_small=check(l)\n",
    "        return r if abs(choose_large-target)<abs(choose_small-target) else l\n",
    "    def binarySearch(self,arr,i):\n",
    "        l,r=0,len(arr)-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if arr[mid]<i:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left, right = 0, max(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            res = sum([n if n <= mid else mid for n in arr])\n",
    "\n",
    "            if res < target:\n",
    "                left = mid + 1\n",
    "            elif res > target:\n",
    "                right = mid\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        res1 = sum([n if n <= (left - 1) else (left - 1) for n in arr])\n",
    "        res2 = sum([n if n <= left else left for n in arr])\n",
    "\n",
    "        if abs(res1 - target) > abs(res2 - target):\n",
    "            return left\n",
    "        else:\n",
    "            return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        total = sum(arr)\n",
    "        if total <= target:\n",
    "            return max(arr)\n",
    "        n = len(arr)\n",
    "        val = target // n\n",
    "        total, last = 0, 0\n",
    "        while total < target:\n",
    "            last = total\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                total += arr[i] if val > arr[i] else val\n",
    "            val += 1\n",
    "        return val - 2 if abs(target - total) >= abs(target - last) else val - 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp1 = 0\n",
    "            for num in arr:\n",
    "                if num > mid:\n",
    "                    tmp1 += mid\n",
    "                else:\n",
    "                    tmp1 += num\n",
    "            if tmp1 >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        tmp1 = 0\n",
    "        for num in arr:\n",
    "            if num > left:\n",
    "                tmp1 += left\n",
    "            else:\n",
    "                tmp1 += num\n",
    "        \n",
    "        tmp2 = 0\n",
    "        for num in arr:\n",
    "            if num > left-1:\n",
    "                tmp2 += (left-1)\n",
    "            else:\n",
    "                tmp2 += num\n",
    "\n",
    "        if tmp1 - target < target - tmp2:\n",
    "            return left\n",
    "        else:\n",
    "            return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        def Check(threshold):\n",
    "            i = 0\n",
    "            the_sum = 0\n",
    "            while i < n:\n",
    "                if arr[i] <= threshold:\n",
    "                    the_sum += arr[i]\n",
    "                else:\n",
    "                    break\n",
    "                i += 1\n",
    "            the_sum += (threshold * (n - i))\n",
    "            return the_sum\n",
    "\n",
    "        arr.sort()\n",
    "        #print('arr:', str(arr))\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = arr[-1]\n",
    "        ans = 0\n",
    "        min_diff = float('inf')\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            the_sum = Check(mid)\n",
    "            #print('%d,%d,%d -> %d' % (left, mid, right, the_sum))\n",
    "            if the_sum > target:\n",
    "                diff = the_sum - target\n",
    "                if diff < min_diff:\n",
    "                    ans = mid\n",
    "                    min_diff = diff\n",
    "                elif diff == min_diff:\n",
    "                    if mid < ans:\n",
    "                        ans = mid\n",
    "                right = mid - 1\n",
    "            elif the_sum == target:\n",
    "                if min_diff > 0:\n",
    "                    ans = mid\n",
    "                else:\n",
    "                    if arr[mid] < ans:\n",
    "                        ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                diff = target - the_sum\n",
    "                if diff < min_diff:\n",
    "                    ans = mid\n",
    "                    min_diff = diff\n",
    "                elif diff == min_diff:\n",
    "                    if mid < ans:\n",
    "                        ans = mid\n",
    "                left = mid + 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        pre = [*accumulate(arr, initial=0)]\n",
    "\n",
    "        def get_total(v):\n",
    "            i = bisect_left(arr, v)\n",
    "            return (n - i) * v + pre[i]\n",
    "    \n",
    "        l = target // n\n",
    "        r = arr[-1]\n",
    "        while r > l:\n",
    "            mid = l + r >> 1\n",
    "            total = get_total(mid)\n",
    "            if total > target:\n",
    "                r = mid - 1\n",
    "            elif total < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        return min((l-1, l, l+1), key=lambda i:abs(get_total(i) - target))   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = [0]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1] + num)\n",
    "        \n",
    "        left, right = 1, max(arr)  # Fix the variable assignment\n",
    "        result = 0\n",
    "        diff = target\n",
    "        \n",
    "        while left <= right:  \n",
    "            mid = left + (right - left) // 2\n",
    "            it = bisect_left(arr, mid)\n",
    "            cur = prefix[it] + (n - it) * mid\n",
    "\n",
    "            if abs(cur - target) < diff:\n",
    "                result, diff = mid, abs(cur - target)\n",
    "\n",
    "            if cur < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2. 解法二: 二分法 寻找小于等于某个数的最大值- 右边界搜索 左闭右闭区间\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = max(arr)\n",
    "        # 寻找小于等于target的最大值\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calculate(arr, mid) <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        sum1 = self.calculate(arr, left)\n",
    "        sum2 = self.calculate(arr, left - 1)\n",
    "        if abs(sum1 - target) < abs(sum2 - target):\n",
    "            return left\n",
    "        return left - 1\n",
    "\n",
    "    def calculate(self, arr, value):\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            res += min(num, value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        presum = [0]\n",
    "        for a in arr:\n",
    "            presum.append(presum[-1]+a)\n",
    "        if(presum[-1] <= target):\n",
    "            return arr[-1]\n",
    "        def getSum(x):\n",
    "            left, right = 0, n-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)>>1\n",
    "                if(arr[mid] <= x):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return presum[left] + x*(n-left)\n",
    "        left, right = 0, 10**5\n",
    "        while(left <= right):\n",
    "            mid = (left+right)>>1\n",
    "            print(mid , getSum(mid))\n",
    "            if(getSum(mid) >= target):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        mindiff = float('inf')\n",
    "        result = None\n",
    "        for num in range(right, left+1):\n",
    "            if(abs(getSum(num)-target) < mindiff):\n",
    "                result = num \n",
    "                mindiff = abs(getSum(num)-target)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        if not arr: return -1\n",
    "\n",
    "        left, right = 0, max(arr)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            total_sum = sum(min(mid, num) for num in arr)\n",
    "            # 找第一个使得总和超过 target 的 mid\n",
    "            if total_sum <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        sum_left = sum(min(left, num) for num in arr)\n",
    "        sum_left_minus_one = sum(min(left - 1, num) for num in arr)\n",
    "        if abs(sum_left - target) < abs(sum_left_minus_one - target):\n",
    "            return left\n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        prefix = [0]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1] + num)\n",
    "        r, ans, diff = max(arr), 0, target\n",
    "        for i in range(1, r + 1):\n",
    "            it = bisect.bisect_left(arr, i)\n",
    "            cur = prefix[it] + (n - it) * i \n",
    "            if abs(cur - target) < diff:\n",
    "                ans, diff = i, abs(cur - target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()  #arr升序排序处理\n",
    "        pre=0       #arr[](升序后)的前缀合（含首0）\n",
    "        for i, a in enumerate(arr):\n",
    "            k=len(arr)-i        # 后面还有k项，同时k也是S(a)在a=arr[i]处的斜率！\n",
    "            d=pre+a*k-target    #前i项和pre + 后k项全置为arr[i] 与 target差值\n",
    "            if d>=0: \n",
    "                return a - int((d/k)+0.5)  #等价于 arr[i] - 四舍五入(d÷k) 。\n",
    "            pre+=a  #↑当d÷k的小数部分为0.5，则取1（注意整体是减去1）符合同近取小原则。\n",
    "        return arr[-1]  #for循环内无解，取arr[]最大值作为结果。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 返回 数组和\n",
    "    def calcSum(self, arr:[int], value:int, presum:[int]) -> int:\n",
    "        left, right = 0, len(arr)-1\n",
    "        while left<right:\n",
    "            mid = left+right>>1\n",
    "            if arr[mid] < value:\n",
    "                left = mid+1\n",
    "            else: right = mid\n",
    "        return presum[left] + value*(len(arr)-left)\n",
    "        \n",
    "    \n",
    "    # 返回第一个满足 数组和大于target的value\n",
    "    def binarySearchValue(self, arr:[int], target:int, presum:[int]) -> int:\n",
    "        left, right = 0, arr[-1]\n",
    "        while left<right:\n",
    "            mid = left+right>>1\n",
    "            if self.calcSum(arr, mid, presum) < target:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        size = len(arr)-1\n",
    "        presum = [0]*(size+1)\n",
    "        for i in range(size):\n",
    "            presum[i+1] = arr[i] + presum[i]\n",
    "        value = self.binarySearchValue(arr, target, presum)\n",
    "        sum1 = self.calcSum(arr, value, presum)\n",
    "        sum2 = self.calcSum(arr, value-1, presum)\n",
    "        diff1 = abs(sum1-target)\n",
    "        diff2 = abs(sum2-target)\n",
    "    \n",
    "        return value if diff1 < diff2 else value-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        arr.sort()\n",
    "        n=len(arr)\n",
    "        sam=sum(arr)\n",
    "        if sam<=target:\n",
    "            return arr[-1]\n",
    "            \n",
    "        def check(x):\n",
    "            return sum(v if v<=x else x for v in arr)\n",
    "        \n",
    "        l,r=0,arr[-1]\n",
    "        while l<r:\n",
    "            m=(l+r)>>1\n",
    "            if check(m)>=target:\n",
    "                r=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        \n",
    "        a=check(l)-target\n",
    "        b=target-check(l-1)\n",
    "        print(l,a,b)\n",
    "        return l if a<b else l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def calcu(self, arr, value, pre_sum):\n",
    "        size = len(arr)\n",
    "        left, right = 0, size - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] < value:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return pre_sum[left] + (size - left) * value\n",
    "\n",
    "    def binary_search(self, arr, target, pre_sum):\n",
    "        left, right = 0, arr[-1]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.calcu(arr, mid, pre_sum) < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def findBestValue(self, arr: List[int], target: int) -> int:\n",
    "        size = len(arr)\n",
    "        arr.sort()\n",
    "        pre_sum = [0 for _ in range(size + 1)]\n",
    "        for i in range(size):\n",
    "            pre_sum[i + 1] = pre_sum[i] + arr[i]\n",
    "\n",
    "        value = self.binary_search(arr, target, pre_sum)\n",
    "\n",
    "        sum_1 = self.calcu(arr, value, pre_sum)\n",
    "        sum_2 = self.calcu(arr, value - 1, pre_sum)\n",
    "\n",
    "        diff_1 = abs(sum_1 - target)\n",
    "        diff_2 = abs(sum_2 - target)\n",
    "\n",
    "        return value if diff_1 < diff_2 else value - 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
